Гливка Антон Георгійович

ВВЕДЕННЯ

1. АКТУАЛЬНІСТЬ ТЕМИ

2. ЗВ'ЯЗОК РОБОТИ З НАУКОВИМИ ПРОГРАМАМИ, ПЛАНАМИ, ТЕМАМИ

3. МЕТА ТА ЗАДАЧІ РОЗРОБКИ Й ДОСЛІДЖЕННЯ

4. ОЧІКУВАНА НАУКОВА НОВИЗНА

5. ПРАКТИЧНЕ ЗНАЧЕННЯ ОТРИМАНИХ РЕЗУЛЬТАТІВ

6. АПРОБАЦІЯ РОБОТИ

7. ОГЛЯД ДОСЛІДЖЕНЬ І РОЗРОБОК ПО ТЕМІ

8. ОПИС РОЗРОБЛЯЄМОЇ ПІДСИСТЕМИ

9. МЕТОДИ Й ЗАСОБИ ДОСЛІДЖЕННЯ Й РІШЕННЯ ПОСТАВЛЕНОГО ЗАВДАННЯ

10. ОПИС ОТРИМАНИХ І ПЛАНОВАНИХ РЕЗУЛЬТАТІВ

ВИСНОВКИ

СПИСОК ЛІТЕРАТУРИ

*Важливе зауваження

Сучасне промислове підприємство являє собою складну багаторівневу систему. Модуль планування виробництва в системах планування й керування підприємством будується на основі математичних моделей процесів на підприємстві, від точності яких залежить оптимальність розроблювальних об'ємно-календарних планів.

Одним з найважливіших методів дослідження й побудови системи керування промисловим підприємством є моделювання. Сучасна система керування заводом не може бути представлена без використання моделей як кількісної підстави ухвалення рішення при організації, плануванні й регулюванні виробництва.

Під моделлю розуміється подумки або матеріально створена конструкція, що відтворює основні, найбільш істотні риси даного економічного явища. Модель відображає величини, що визначають характеристику даного господарського процесу, відтворює його основні ознаки й зв'язки. Вона не є повним описом реального економічного життя у всій її складності, у ній опущені другорядні, побічні елементи й властивості, що не роблять на результат процесу істотного впливу.

Моделі можуть бути представлені графічно, наприклад, графік функції двох змінних або мережна модель керування складним комплексом робіт; у вигляді числових моделей-матриць, таблиць чисельних значень змінних й їхніх коефіцієнтів, аналітичних виражень математичних рівнянь та ін.

Незалежно від виду моделі, моделювання економічного процесу побудовано на поданні його в математичному виді. Математична модель відтворює в кількісній формі у вигляді співвідношень (рівнянь, нерівностей, тотожностей) якісні закономірності, істотні взаємозв'язки господарської діяльності.

>> зміст

Особливу значимість має завдання оперативно-календарного планування, що значною мірою впливає на результати роботи підприємства в цілому.

Для підприємств дискретного типу виробництва характерно позаказне планування в умовах великої розмаїтості номенклатури випускає продукции, що, і технологічних операцій. Все це значно ускладнює завдання оперативного календарного планування на таких підприємствах.

Висока розмірність даного завдання й стахостичність характеристик затрудняє використання детермінованих методів для її рішення, а методи, засновані на евристиках, не завжди дозволяють одержати досить гарні рішення.

Більшість розроблених до теперішнього часу методик оперативно-календарного планування засновано на спрощених моделях завдання, що знижує їхню практичну значимість, або ці методики застосовні лише для певних специфічних умов.

Значну складність, крім того, представляє проблема оцінки якості одержуваних розкладів.

Таким чином, існує необхідність у розробці методики оперативного календарного планування роботи підприємств дискретного виробництва, що дозволила б проводити оптимізацію розкладу випуску продукції по декількох критеріях якості з урахуванням існуючих обмежень, формувати змінно-добові завдання підрозділам цеху й при цьому забезпечувала б одержання оптимальних або близьких до оптимальних рішень.

>> зміст

Кваліфікаційна робота магістра виконувалася протягом 2008-2009 р. відповідно до наукових напрямків кафедри «Автоматизовані системи керування» Донецького національного технічного університету.

>> зміст

Ціль роботи

Метою роботи є теоретичне обґрунтування й розробка моделей і методів для підвищення ефективності роботи машинобудівного підприємства за рахунок складання субоптимальних розкладів роботи на двох рівнях - на рівні виробництва й на рівні цеху, на підставі обраних критеріїв оптимізації.

Ідея роботи

Шляхом використання сучасних методів обробки й інтелектуального аналізу даних, створити комп'ютерну підсистему, що зможе оперативно реагувати на зміну обстановки у виробництві (поломка встаткування, недостача матеріалу ...), у наслідку чого змінювати (створювати) план, що буде оптимальним у даній ситуації.

Це дозволить на практиці швидко й ефективно вирішувати завдання оперативно-виробничого планування. Розроблений програмний модуль дозволить скоротити витрату матеріальних і тимчасових ресурсів на виконання планування виробничого процесу, підвищить якість обробки інформації і якість результату обробки, виключивши помилки, пов'язані з людським фактором.

Основні завдання розробки й досліджень

Для реалізації ідеї й досягнення мети магістерської роботи поставлені наступні завдання:

     - проаналізувати методичні й теоретичні матеріали по математичних моделях машинобудівного виробництва;

     - аналіз існуючих методів штучного інтелекту, використовуваних для оперативного планування; порівняння методів і вибір найкращого, що дозволяє одержати оптимальний розклад виробничих робіт;

     - проаналізувати системи обробки даних і вибрати інструментарій для досягнення поставленої мети магістерської роботи;

     - виконати аналіз критеріїв і методів оперативного планування виробництва на машинобудівному підприємстві;

     - розробити програму для одержання субоптимальних розкладів, керуючись вивченими теоретичними відомостями.

     - експериментальне випробування програмного модуля на реальних даних.

Предмет розробки й досліджень

Предметом розробки й дослідження є комп'ютерна підсистема для оптимізації оперативного планування виробництва в машинобудуванні, що дозволить реагувати на будь-які зміни в процесі виробництва й оперативно становити розклади роботи на виробничих ділянках.

Об'єкт розробки й досліджень

Об'єктом дослідження в даній роботі буде процес оперативного планування випуску продукції в умовах АТ «НОРД».

Методологія й методи досліджень

Методологічну основу дослідження склали положення системного аналізу, методи планування виробничої програми підприємства, економіко-математичні методи й моделі, експертні методи, методи прийняття управлінських рішень. Для розробки комп'ютерної підсистеми оперативного планування виробництва в машинобудуванні обраний мурашиний алгоритм, що дає найбільш гарні результати в порівнянні з іншими інноваційними методами, і генетичні алгоритми, що адекватно враховують основні закономірності виробництва й реалізації продукції на основі процесів природного добору.

>> змiст

До останнього десятиліття минулого століття в побудові систем керування домінував традиційний підхід: лінійні, нелінійні, адаптивні методи й ін. Однак такий підхід не завжди дозволяє здійснювати робасне керування складними нестаціонарними об'єктами. Дана обставина послужила розвитку нового наукового напрямку - інтелектуальних систем керування.

Інтелектуальні системи керування - це системи керування, здатні до “розуміння” і навчанню відносно об'єкта керування, збурювань, зовнішнього середовища й умов роботи. Основна відмінність інтелектуальних систем - наявність механізму системної обробки знань. Головна архітектурна особливість, що відрізняє інтелектуальні системи керування від традиційних, - це механізм одержання, зберігання й обробки знань для реалізації своїх функцій.

Існує кілька сучасних технологій, що дозволяють створювати системи керування такого типу: експертні системи, штучні нейронні мережі, нечітка логіка, генетичні алгоритми й ряд інших. Інтелектуальні технології між собою розрізняє насамперед те, що саме покладено в основу концепції інтелектуальності - або вміння працювати з формалізованими знаннями людини (експертні системи, нечітка логіка), або властиві людині прийоми навчання й мислення (штучні нейронні мережі й генетичні алгоритми).

Сьогодні ніхто не заперечує, що новий підхід до оптимізації, такий як мурашиний алгоритм, є дуже перспективним у рішенні NP-важких завдань. З іншої сторони генетичний алгоритм високо ефективний при рішенні завдань глобальної оптимізації. Таким чином, що інтригує представляється саме сполучення генетичного алгоритму й мурашиного алгоритму. Це сполучення дозволить створити алгоритм вирішальне завдання оптимізації значно краще, ніж ці ж методи окремо.

Тому метою роботи є реалізація програмного модуля на основі методів штучного інтелекту, що дозволяє ефективно виконувати оперативне календарне планування на двох рівнях, на рівні підприємства й на цеховому рівні.

>> зміст

Практична значимість отриманих результатів полягає в розробці підсистеми оперативно-виробничого планування виробництва. Розроблений програмний модуль дозволить скоротити витрату матеріальних і тимчасових ресурсів на виконання планування виробничого процесу, підвищить якість обробки інформації і якість результату обробки, виключивши помилки, пов'язані з людським фактором.

>> зміст

Апробація роботи планується на вересень 2009 року, під час проходження переддипломної практики, безпосередньо на машинобудівному підприємстві (АТ «НОРД»). Будуть зроблені експериментальні дослідження, на підставі яких будуть обрані критерії алгоритмів оптимізації, які будуть давати кращі результати.

>> зміст

На локальному рівні (у межах ДонНТУ) портал магістрів може надати інформацію про 3 роботи на подібну тему, підхід яких абсолютно різний. Також цією проблемою займаються професор кафедри АСУ, д.т.н. Лаздинь С.В. і доцент кафедри АСУ, к.т.н. Секірін О.І.

На глобальному рівні, проблема оперативного планування виробництва вирішується. Створено ряд програмних продуктів, які можна віднести до ERP систем, але алгоритм роботи цих систем має ряд недоліків, оптимізація роботи, на даний момент, не здійснюється, системи просто використають знання про виробничий процес і прораховують модель виробництва.

Основні недоліки цих систем:

     - висока вартість покупки;

     - проблеми впровадження через невідповідність конфігурації систем з поставленим завданням;

     - утруднення супроводу продукту у зв'язку з територіальною віддаленістю.

>> зміст

Оперативне планування являє собою здійснення поточної діяльності планово-економічних служб протягом короткого періоду, наприклад, розробка місячної виробничої програми, складання квартальних бюджетів підприємства, контроль і коректування отриманих результатів і т.п.[1]

Оперативне планування виробництва є завершальною ланкою планової роботи на підприємстві - продовженням і конкретизацією завдань техпромфінплану. Воно полягає в розробці на основі річних (квартальних) планів конкретних виробничих завдань на короткі проміжки часу як для підприємства в цілому, так і для його підрозділів й в оперативному регулюванні ходу виробництва за даними оперативного обліку й контролю.[2]

Особливістю цього виду планування є сполучення розробки планових завдань із організацією їхнього виконання.[1]

В обсяг робіт по оперативному плануванню входить:

     - розробка прогресивних календарно-планових нормативів руху виробництва;

     - складання оперативних планів і графіків для цехів, ділянок, бригад і робочих місць й їхнє доведення до безпосередніх виконавців;

     - оперативний облік і контроль ходу виробництва, попередження й виявлення відхилень від передбачених планів і графіків і забезпечення стабілізації ходу виробництва.

Календарне планування включає розподіл річних планових завдань по виробничих підрозділах і строкам виконання, а також доведення встановлених показників до конкретних виконавців робіт. З його допомогою розробляються змінно-добові завдання, і погодиться послідовність виконання робіт окремими виконавцями.

При реалізації розробленого календарного плану ведеться оперативний облік ходу його виконання - здійснюється збір інформації про фактичне виконання плану, її переробка й передача відповідним службам підприємства.

Оперативне планування виробництва по місцю його виконання ділиться на міжцехове й внутрішньо цехове.[2]

Міжцехове планування забезпечує розробку, регулювання й контроль виконання планів виробництва й продажі продукції всіма цехами підприємства, а також координує роботу основних, проектно-технологічних, планово-економічних й інших функціональних служб.

На машинобудівних підприємствах, як правило, виробничі програми розробляються й видаються цехам плановими службами на черговий рік із квартальною й місячною розбивкою.

Змістом внутрішньо цехового планування є розробка оперативних планів і складання поточних графіків роботи виробничих ділянок, потокових ліній й окремих робочих місць на основі річних планів виробництва й продажі продукції основних цехів підприємства.

У сучасному виробництві широко поширені різні системи оперативного планування, обумовлені як внутріфірмовими факторами, так і зовнішніми ринковими умовами.

Під системою оперативного планування виробництва в економічно літературі прийнято розуміти сукупність різних методик технологій планової роботи, що характеризуються ступенем централізації, об'єктом регулювання, составом календарно-планових показників, порядком обліку й руху продукції й оформлена обліковою документацією.[3]

Оперативне планування виробництва полягає в розробці найважливіших об'ємних календарних показників виробничо-господарської діяльності підприємства. Усякий процес оперативного планування передбачає виконання економістами-менеджерами таких етапів діяльності, як вибір стратегії розвитку підприємства, обґрунтування форми організації виробництва, визначення логістичної схеми руху матеріальних потоків, розробка основних календарно-планових нормативів, оперативне планування роботи виробничих підрозділів організаційна підготовка виробництва, безпосередня організація оперативної роботи, що тече контроль і регулювання ходу виробництва.

В оперативному плануванні виробництва залежно від розроблювальних показників застосовуються такі основні методи, як об'ємний, календарний, а також їхнього різновиду: об'ємно-календарний й об'ємно-динамічний.[4]

Можна зробити вивід, що оперативне планування виробництва, як свідчить передовий досвід, відіграє головну роль у забезпеченні своєчасного випуску й поставки продукції споживачам на основі раціонального використання обмежених економічних ресурсів у поточному періоді часу. Подальший розвиток оперативного планування на вітчизняних підприємствах буде сприяти рішенню наступних організаційно-економічних завдань:

     - досягнення погодженої роботи всіх ланок виробництва на основі єдиної ринкової мети, що передбачає рівномірний випуск і збут товарів;

     - удосконалювання всієї системи внутріфірмового планування за рахунок підвищення надійності календарно-планових розрахунків і зниження трудомісткості;

     - підвищення гнучкості й оперативності внутрішньогосподарського планування на основі більше повного обліку вимог споживачів і наступного коректування річних планів;

     - забезпечення безперервності в процесі виробничого планування й досягнення більше тісної взаємодії стратегічних, тактичних й оперативних планів;

     - створення на кожнім підприємстві системи оперативного планування виробництва, що відповідає сучасним вимогам ринку й рівню розвитку конкретного підприємства.

Удосконалювання оперативно-виробничого планування на вітчизняних підприємствах буде сприяти підйому виробництва й росту ефективності в умовах діючих ринкових відносин.

Таким чином, можна сказати, що основне завдання оперативного планування зводиться в остаточному підсумку до забезпечення на підприємстві злагоджений і ритмічний ходи всіх виробничих процесів з метою найбільшого задоволення основних потреб ринку, раціонального використання наявних економічних ресурсів і максимізації одержуваного прибутку.[2]

Завдання оперативного планування виробництва можна розбити на декілька подзадач, черговість і залежність яких показана на малюнку 8.1.

Рисунок 8.1 - Ієрархія оперативного планування виробництва

На рисунку 8.1 представлена черговість операцій при формуванні оперативних планів виробництва.

Як видно з малюнка планово-економічний відділ повинен передати в підсистему оперативного планування виробництва дані про замовлення за квартал. Далі необхідно розподілити завдання таким чином, щоб виконати умови по договорах із замовниками точно в строк, або з мінімальною затримкою, при цьому необхідно точно скласти графік зборки виробів на місяць (кількість виробів і строки випуску), щоб зібрати готову продукцію для різних замовлень у повному обсязі. Із графіка зборки випливає потреба в деталях і вузлах, для виготовлення яких відповідно до технологічного процесу необхідно певний час. Далі необхідно сформувати партії запуску деталей і строки з урахуванням випередження, щоб до моменту зборки вузла, всі деталі, з яких він складається, були вже готові. Відповідно до технологічного маршруту виготовлення деталей і вузлів необхідно сформувати розклади роботи ділянок на добу, зміни, годинники.

>> зміст

Методи моделювання

Моделювання можливо з використанням наступних методів:

     - Імітаційні моделі;

     - Математичне моделювання;

     - Теорія графів і мереж;

     - Теорія масового обслуговування;

     - Об’ектно-орієнтований підхід;

     - Теорія розкладів.

Імітаційні моделі

Основними вимогами до імітаційних моделей є адекватність моделі, максимальна наближеність алгоритмів до методології об'єктного програмування й універсальність, як можливість подання всього безлічі дискретних станів системи. Використання в імітаційному моделюванні мереж Петрі, як найбільш універсального й часто, що зустрічається методу, формалізації імітаційних моделей, у більшості випадків, обмежено побудовою нескладних циклічних моделей з доступним для огляду кількістю стану системи.[5]

При моделюванні роботи цехів даним образом можна виділити наступні особливості:

     1) за рахунок властивості масштабування мережі в часі з'являється можливість аналізу стану всіх об'єктів на будь-якому розрізі мережі;

     2) можливість створення мереж будь-якої складності й розмірності, як функції від часу й кількості полюсів мережі, що представляють собою ЕП;

     3) можливість моделювання на вже створеній мережі в межах будь-яких інтервалів часу, з різних, що цікавлять проектанта подій;

     4) можливість оцінки розкладів роботи встаткування;

     5) максимальна наближеність логіки синтезу мереж до логіки побудови програмного забезпечення;

     6) можливість використання модульної структури програмного забезпечення процесу моделювання.

Математичне моделювання

Одним з основних вимог, пропонованих до підсистем оперативно-календарного планування (ОКП), є точність формованого розкладу робіт. Точність будь-якої моделі, як правило, залежить від повноти її подання, адекватності умовам реальної виробничої системи. У більшості моделей ОКП розклад традиційно будувалася щодо основного класу обслуговуючих пристроїв. Модель розкладу, методика й алгоритм його формування при виконанні різних партій деталей (так званих партій-операцій) і впливу інших технологічних факторів представлені в роботі.[6]

На безлічі номенклатури деталей, представленій безліччю одиниць планування (ОП), якими є партії-операції, М и безліччю обслуговуючих пристроїв, необхідно скласти оптимальний розклад. Графічна інтерпретація довільної моделі розкладу для випадку представляється діаграмою Ганта. Узагальнена математична модель для оперативно-календарного планування, що включає наступні елементи:

     - втрати часу, при надходженні нових партій деталей;

     - втрати часу, пов'язані з очікуванням партій деталей, що перебувають у необхідний момент на обробці на попередній операції;

     - втрати часу, пов'язані з очікуванням партій деталей, що перебувають у процесі транспортування;

     - втрати часу, пов'язані з очікуванням партій деталей, що перебувають у процесі транспортування.

Отримана модель оптимізується одним із чисельних методів і виходить оптимальне рішення на зазначеному тимчасовому інтервалі. Обрієм планування розклади може бути 8-ми годинна зміна. Недоліками даного виду моделювання є те, що оперативне планування, є досить складною динамічною системою, математична модель якої описується досить складними рівняннями, складання яких неможливо без певного роду допущень, що позначається на її точності.[7]

Теорія графів і мереж

Для дослідження систем які складаються з різнорідних елементів застосовують апарат теорії мереж масового обслуговування (ТММО). Мережа масового обслуговування являє собою сукупність систем масового обслуговування, у якій циркулюють заявки, переходячи з однієї системи в іншу. В основі ТММО лежить мережний опис технологічного процесу обробки виробу. Мережа, при цьому відображає взаємозв'язку між автономно функціонуючими елементами й підсистемами. Мережа являє собою граф, що складається з безлічі вузлів й орієнтованих дуг, що з'єднують вузли. При мережному поданні структури цехів вузли виступають як автономні агрегати або позиції обробки, дуги показують напрямок потоку заявок (виробів) у системі. Залежно від поставленого завдання й досліджуваної функції змінюється число вузлів у мережі, їхній состав і зв'язки між ними.[8]

Теорія масового обслуговування

Дані моделі ґрунтуються на гіпотезі, про імовірнісний характер протікання процесів і взаємодії встаткування.[9] При моделюванні роботи цехів (за допомогою апарата Q-схем), використаються допущення:

     - послідовність виконання операцій технологічних маршрутів. Технологічний маршрут використається тільки для розрахунку розподілу ймовірностей частоти й тривалості перебування виробів на робочих позиціях;

     - виробнича система розглядається як замкнута система, тобто в кожен момент часу в ній перебуває постійна кількість виробів;

     - кожна робоча позиція має накопичувач необмеженої ємності.

Об’ектно-орієнтований підхід

Є підкласом імітаційних моделей. До найбільш потужних і виразних моделей подання знань про дискретні процеси в реальному часі (РЧ) ставиться продукціонна система. Однак при описі складних процесів моніторингу, контролю й керування з використанням великого числа зовнішніх дискретних об'єктів виникає ряд добре відомих труднощів. Тепер використається нова об’ектно-продукціонна модель знань (ОПМЗ), що є результатом декомпозиції продукціонної моделі системи реального часу "ПРОДУС" на основі об’ектно-орієнтованого підходу. У ній усунуті такі недоліки продукціонної моделі, як відсутність засобів структуризації й декомпозиції бази правил, механізму реального распаралелювання й повторного використання знань, а також запропонований новий децентралізований механізм явного керування інтерпретацією й синхронізацією паралельних об'єктів.[10]

Його переваги в порівнянні із традиційним імітаційним моделюванням можна віднести:

     - простота систематизації й структурування компонентів;

     - спадкування дозволяє реалізовувати складні моделі з різними модифікаціями, а значить його можна застосовувати до конкретної системи, без додаткового перепрограмування;

     - облік асинхронності й распаралелювання.

Теорія розкладів

Якість функціонування сучасного виробництва багато в чому визначається рішеннями, прийнятими на етапах календарного планування й оперативного керування. Особливо це актуально у зв'язку зі створенням сучасних автоматизованих виробництв - гнучких виробничих систем (ГВС). Системи оперативно - календарного планування сучасних виробництв будуються в тому числі й на досягненнях так називаної «теорії розкладів».

Теорія розкладів - це наука, що займається дослідженнями детермінованих обслуговуючих систем на предмет оптимізації розкладів їхнього функціонування.[11]

Приклади таких систем:

     - цех, ділянка, на верстатах яких здійснюється обробка деталей;

     - ВУЗ, де викладачі навчають студентів і т.д.

Розклад - деяка сукупність вказівок щодо того, які саме вимоги якими саме приладами обслуговуються в кожен момент часу.

Приклад. На рисунку 9.1 наведений графік розкладу Si(t), iє обслуговування вимог N={1,2,3,4} приладами M={1,2,3} при різних маршрутах обслуговування вимог. Усе тривалості обслуговування рівні «1».

Рисунок 9.1 - Графік розкладу обслуговування вимог N = {1, 2, 3, 4} приладами M = {1, 2, 3}

Методи оптимізації

Якщо існує кілька припустимих розкладів, то природно необхідно вибрати краще з них.

Оптимальний розклад може бути знайдене в результаті перебору кінцевої безлічі можливих варіантів. Основні труднощі при цьому полягає в тому, що число таких варіантів дуже велике й росте, щонайменше, экспоненціально з ростом розмірності завдання. Відомі так називані евристичні алгоритми формування розкладів, алгоритми на основі методів лінійного й динамічного програмування. Завдання складання розкладів для деяких складних систем обслуговування дотепер не вирішені (NP - важкі завдання).

Метод галузей і границь

Методологічну основу дослідження склали положення системного аналізу, методи планування виробничої програми підприємства, економіко-математичні методи й моделі, експертні методи, методи прийняття управлінських рішень. Для розробки комп'ютерної підсистеми оперативного планування виробництва в машинобудуванні обраний мурашиний алгоритм, що дає найбільш гарні результати в порівнянні з іншими інноваційними методами, і генетичні алгоритми, що адекватно враховують основні закономірності виробництва й реалізації продукції на основі процесів природного добору.[12]

Метод галузей і границь - один з комбінаторних методів. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються по певних ознаках перспективними, і відкиданні безперспективних варіантів.

Метод галузей і границь полягає в наступному: безліч припустимих рішень (планів) деяким способом розбивається на підмножини, кожне з яких цим же способом знову розбивається на підмножини. Процес триває доти, поки не отримане оптимальне целочислене рішення вихідного завдання.

Генетичні алгоритми

Одними із сучасних методів оптимізації, заснованих на евристичних алгоритмах, є генетичні алгоритми.

Генетичний алгоритм був отриманий у процесі узагальнення й імітації в штучних системах таких властивостей живої природи, як природний добір, пристосовність до умов, що змінюються, середовища, спадкування нащадками життєво важливих властивостей від батьків і т.д. Тому що алгоритм у процесі пошуку використає деяке кодування безлічі параметрів замість самих параметрів, то він може ефективно застосовуватися для рішення завдань дискретної оптимізації, певних як на числових безлічах, так і на кінцевих безлічах довільної природи. Оскільки для роботи алгоритму як інформація про оптимізіруєму функцію використаються лише її значення в розглянутих крапках простору пошуку й не потрібно обчислень ні похідних, ні яких-небудь інших характеристик, те даний алгоритм застосуємо до широкого класу функцій, зокрема, що не мають аналітичного опису. Використання набору початкових крапок дозволяє застосовувати для їхнього формування різні способи, що залежать від специфіки розв'язуваного завдання, у тому числі можливе завдання такого набору безпосередньо людиною.[13]

Сила генетичних алгоритмів у тім, що цей метод дуже гнучкий, і, будучи побудованим у припущенні, що про навколишнє середовище нам відомий лише мінімум інформації (як це часто буває для складних технічних систем), алгоритм успішно справляється із широким колом проблем, особливо в тих завданнях, де не існує загальновідомих алгоритмів рішення або високий ступінь апріорної невизначеності.

Механізм простого ГА (ПГА) нескладний. Він копіює послідовності й переставляє їхньої частини. Попередньо ГА випадково генерує популяцію послідовностей - стрінгов (хромосом). Потім ГА застосовує безліч простих операцій до початкової популяції й генерує нові популяції.

ПГА складається з 3 операторів: репродукція, кроссінговер, мутація.

Репродукція - процес, у якому хромосоми копіюються відповідно до їх цільової функції (ЦФ). Копіювання хромосом з «кращим» значенням ЦФ має більшу ймовірність для їхнього влучення в наступну генерацію. Оператор репродукції (ОР), є штучною версією натуральної селекції, «виживання найсильніших» по Дарвіну.

Після виконання ОР оператор кроссинговера (ОК) може виконатися в кілька кроків. На першому кроці вибираються члени нового репродукованої безлічі хромосом. Далі кожна пара хромосом (стрингов) перетинається за наступним правилом: ціла позиція k уздовж стринга вибирається випадково між 1 і довжиною хромосоми мінус одиницю тобто в інтервалі (1,L-1). Довжина L хромосоми це число значущих цифр у його двійковому коді. Число k, обране випадково між першим й останнім членами, називається крапкою ОК або поділяючим знаком.

Механізм ОР й ОК включає випадкову генерацію чисел, копіювання хромосом і частковий обмін інформацією між хромосомами.

Генерація ГА починається з репродукції. Ми вибираємо хромосоми для наступної генерації, обертаючи колесо рулетки, така кількість разів, що відповідає потужності початкової популяції. Величину відносини Fi(x)/Sum(x) називають імовірністю вибору копій (хромосом) при ОР і позначають Pi(OP). Тут Fi(x) - значення ЦФ i-тої хромосоми в популяції, Sum(x) - сумарне значення ЦФ всіх хромосом у популяції. Величину Pi(OP) також називають нормалізованою величиною. Очікуване число копій i-ої хромосоми після ОР визначають N=Pi(OP)*n. Тут n - число аналізованих хромосом.

Число копій хромосоми, що переходить у наступне положення, іноді визначають на основі вираження: Ai=Fi(x)/СереднєFi(x).

У багатьох проблемах є спеціальні знання, що дозволяють побудувати аппроксимаційну модель. При використанні ГА це може зменшити обсяг і час обчислень і спростити моделювання функцій, скоротити число помилок моделювання.

Мурашиний алгоритм

Оптимізація в магістерській роботі буде виробляється, в основному, за допомогою мурашиних алгоритмів. Тому, найбільше докладно я зупинюся саме на них.

Основна ідея даного алгоритму є моделювання поводження мурах, колективної адаптації. Колонія являє собою систему з дуже простими правилами автономного поводження особин. Однак, незважаючи на примітивність поводження кожної окремої мурахи, поводження всієї колонії виявляється досить розумним. Таким чином, основою поводження мурашиної колонії служить ниськоуровнева взаємодія, завдяки якому, у цілому, колонія являє собою розумну многоагентну систему. Взаємодія визначається через хімічну речовину - феромона, що відкладає мурахами на пройденому шляху. При виборі напрямку руху мураха виходить не тільки з бажання пройти найкоротший шлях, але й з досвіду інших мурах, інформацію про яке одержуємо через рівень феромонів ребрах. Із часом відбувається процес випару феромонів, що є негативним зворотним зв'язком.[14]

Властивості мурахи

Кожна мураха має власною «пам'ять», у якій буде зберігатися список міст , які необхідно відвідати мурасі k, що перебуває в місті i.

Мурахи володіють «зором», обернено пропорційній довжині ребра: .

Кожна мураха здатна вловлювати слід феромона, що буде визначати бажання мурахи пройти по даному ребру. Рівень феромона в момент часу t на ребрі буде відповідати .

Імовірність переходу мурахи з вершини i у вершину j буде визначатися наступним співвідношенням:

(9.1)

де – емпіричні коефіцієнти.
Неважко помітити, що дане вираження має ефект «колеса рулетки».

Кількість феромона що відкладається:

(9.2)

де – параметр, , що має значення порядку довжини оптимального шляху, - довжина маршруту .

Випар феромона визначається наступним вираженням:

(9.3)

де m – кількість мурах, p – коефіцієнт випару (p=[0..1]).

Модифікації мурашиного алгоритму

«Елітні» мурахи

Елітою називаються мурахи, чиї маршрути краще інших.
Розроблено наступну модифікацію, заснована на знаннях про «елітні» мурахах. Дана модифікація не враховує кількості елітних мурах. Вираження (9.2) для еліти приймає вид:

(9.4)

де – «авторитет» елітних мурах. Таким чином, ми можемо регулювати вплив «елітних» мурах за допомогою коефіцієнта . Оптимальне значення , в основному, буде залежати від розмірності графа, чисельності колонії, часу життя. Його значення багато в чому визначає швидкість збіжності. Це дуже важливо, оскільки в реальних ситуаціях найчастіше доводиться балансувати між якістю рішення й часом роботи.

Початкове розташування колонії

У простому МА прийнято вважати, що в кожній вершині споконвічно перебуває по одній мурасі. У даній роботі представлені наступні стратегії початкового розташування:

«Ковдра» - реалізація стандартного розміщення мурах, у кожній вершині перебувати по одній мурасі. Тоді складність даного алгоритму виражається наступною залежністю – , оскільки n=m;

«Дробовик» - випадковий розподіл мурах на вершини графа, причому необов'язково, щоб чисельності колонії й вершин збігалися;

«Фокусування» - вся колонія перебуває в одній вершині;

«Блукаюча колонія» - у кожен момент часу, тобто на кожній ітерації, вся колонія переміщається у випадково обрану вершину.

Відзначимо, що назви перших трьох запозичені з назв стратегій формування початкової популяції в генетичних алгоритмах (ГА), що також ставляться до класу алгоритмів «природних обчислень». У ході пророблених експериментальних досліджень було з'ясовано, що збіжність МА і якість рішення сильно залежать від початкового розташування колонії.

Приклад роботи мурашиного алгоритму

Розглянемо випадок, показаний на малюнку, коли на оптимальному досі шляху виникає перешкода. У цьому випадку необхідне визначення нового оптимального шляху. Дійшовши до перешкоди, мурахи з рівною ймовірністю будуть обходити її праворуч і ліворуч. Те ж саме буде відбуватися й на звороті перешкоди. Однак, ті мурахи, які випадково виберуть найкоротший шлях, будуть швидше його проходити, і за кілька пересувань він буде більше збагачений феромоном. Оскільки рух мурах визначається концентрацією феромона, те наступні будуть віддавати перевагу саме цьому шляху, продовжуючи збагачувати його феромоном доти, поки цей шлях з якої-небудь причини не стане недоступний.

Рисунок 9.2 - Концепція мурашиних алгоритмів
(анімація: об'єм - 102 Кб; розмір 707х303; кількість циклів повторення - безперервний цикл повторення)

>> зміст

У результаті аналізу існуючих систем планування виявлені наступні недоліки:

     - розроблені моделі не дозволяють ураховувати багато факторів, що впливають на хід виробництва, які для різних підприємств можуть бути індивідуальні;

     - використання тільки математичних методів обмежується неможливістю швидкого реагування на виникаючі ситуації, що вимагають негайного коректування планів.

Для виключення недоліків подібних розробок необхідно використати еволюційні методи, які дозволили б одержувати оптимальні рішення проблем реальних виробничих ситуацій за малий час. При рішенні такі методи розглядають систему планування як чорний ящик, коли на вході задаються різні значення параметрів планування, після чого оцінюється ефективність одержуваних розкладів з погляду ключових показників ефективності.

На основі аналізу існуючих розробок в області еволюційних методів перспективним рішенням складних комбінаторних завдань оптимізації є гібридне використання генетичного й мурашиного алгоритмів. Це дозволить істотно поліпшити систему оперативного планування, тим самим скоротивши час одержання оптимальних або прийнятних виробничих розкладів. Також з появою випадкових подій, що впливають на процес виробництва, дозволить швидко реагувати на зміну й внесення коректив у вихідні дані.

Виходячи з того, що динамічність виробництва, відхилення різного роду, неоднозначно певні критерії оптимізації, а також більша розмірність розв'язуваних завдань і мала стійкість вихідної інформації - все це викликає необхідність побудови таких методів рішення, які задовольняли б наступним основним вимогам:

     - універсальність, тобто придатність до різних типів виробництва

     - можливість обліку різноманітних виробничих обмежень

     - перехід від одного критерію оптимізації до іншому

     - припустимий час рахунку

     - одержання досить близького до оптимального рішення і його оцінка

     - забезпечення документацією, що містить необхідну нормативну й облікову інформацію

     - одержання реально здійсненних змінних завдань, ув'язаних з питаннями стимулювання

     - перевірка змінних завдань і забезпеченості необхідними ресурсами

     - можливість внесення змін у рішення на основі обліку реального виконання завдань і коректування план-графіка

     - зручність і релевантність подання вихідних даних і результатів рішення

Всім перерахованим вимоги задовольняють методи імітаційного моделювання. Крім того, процес розробки аналітичної моделі виробництва надзвичайно складний, а в більшості випадків одержати модель просто неможливо. Проведення експериментів на реальній моделі також неприйнятно. Тому як основний засіб одержання параметрів виробничих систем вирішено використати імітаційні методи.

Як оптимізаціонний апарат для рішення завдання виконання замовлень точно в строк, необхідно використати генетичний алгоритм.

Цей метод дуже гнучкий, і, будучи побудованим у припущенні, що про навколишнє середовище нам відомий лише мінімум інформації (як це часто буває для складних технічних систем), алгоритм успішно справляється із широким колом проблем, особливо в тих завданнях, де не існує загальновідомих алгоритмів рішення або високий ступінь апріорної невизначеності.

У багатьох проблемах є спеціальні знання, що дозволяють побудувати аппроксимаційну модель. При використанні ГА це може зменшити обсяг і час обчислень і спростити моделювання функцій, скоротити число помилок моделювання.

Для оптимізації безпосередньо виробничих завдань цехам і ділянкам необхідно використати, всі частіше використовувані для оптимізаційних завдань, мурашиний алгоритм.

Мурашині алгоритми являють собою новий перспективний метод рішення завдань оптимізації, в основі якого лежить моделювання поводження колонії мурах. Колонія являє собою систему з дуже простими правилами автономного поводження особин. Однак, незважаючи на примітивність поводження кожної окремої мурахи, поводження всієї колонії виявляється досить розумним. Ці принципи перевірені часом - удала адаптація до навколишнього світу протягом мільйонів років означає, що природа виробила дуже вдалий механізм поводження.

Таким чином, оперативно-календарне планування, що становить основу оперативного керування підприємством, дуже трудомістке завдання. Її рішення має важливе значення для роботи всього підприємства. У традиційному підході рішення присутні істотні недоліки, тому в результаті роботи планується одержати нові методи, які будуть ґрунтуватися на системах штучного інтелекту, які дозволяють створювати більше гнучкі моделі, чим методи статистичної обробки інформації.

>> зміст

У ході виконання даного курсового проекту були виконані завдання по аналізі методів і моделей оптимізації, програмних засобів і готових програмних продуктів оперативного планування виробництва в машинобудуванні.

Зроблено аналіз існуючих систем і підсистем, у висновку якого обґрунтована актуальність створення підсистеми оперативного планування виробництва в машинобудуванні.

Результатом аналізу стали пропозиції за структурою магістерської роботи, результати виконання якої зможуть бути використані для оптимізації оперативного планування виробництва в машинобудуванні.

У роботі проведений аналіз, виявлені позитивні й негативні сторони існуючих методів моделювання, моделей й алгоритмів оптимізації. Наведено вагомі аргументи при виборі алгоритмів оптимізації.

Аналіз показав, що найбільш підходящим є використання генетичного алгоритму й мурашиного алгоритму на різних рівнях оптимізації.

Метою розроблювальної підсистеми є підвищення ефективності роботи машинобудівних підприємств за рахунок складання оптимальних планів виробництва й навантаження встаткування.

>> зміст

1. Планирование дискретного производства в условиях АСУ / [Шкурба В.В., Болдырева В.А., Вьюн А.Ф. и др.]. - К. : Техника, 1975. - 296 с.

2. Сачко Н.С. Организация и оперативное управление машиностроительным производством / Н.С. Сачко. - Минск. : Новое знание, 2005. - 635 с.

3. Михайлова Л.В. Формирование и оперативное управление производственными системами на базе поточно-группового производства в автоматизированном режиме / Л.В. Михайлова, Ф.И. Парамонов, А.В. Чудин. - М. : ИТЦ МАТИ, 2002. - 60 с.

4. Сытник В.Ф. АСУП и оптимальное планирование / В.Ф. Сытник. - К. : Вища школа, 1977. - 312 с.

5. Крушевский А.В. Справочник по экономико-математическим моделям и методам / А.В. Крушевский. – К. : Техника, 1982. – 208 с.

6. Первозванский А.А. Математические модели в управлении производством / А.А. Первозванский. - М.: Наука, 1975. – 616 с.

7. Загидуллин Р.Р. Комплексная математическая модель оперативно-календарного планирования в гибких комплексах механической обработки / P.P. Загидуллин // Автоматизация и современные технологии. - 1999. - № 9. - С. 32-24.

8. Введение в теорию графов [Електронний ресурс] / Уилсон Р. - Режим доступа: http://engenegr.ru/2007/05/10/vvedenie_v_teoriju_grafov.html

9. Імітаційне моделювання систем масового обслуговування [Електронний ресурс] / Ю.В. Жерновий. - Режим доступа: http://zyurvas.narod.ru/bibTMO.html

10. Объектно-ориентированное моделирование [Електронний ресурс] / С.С. Гайсарян. - Режим доступа: http://www.citforum.ru/programming/oop_rsis/glava2.shtml

11. Танаев В.С. Введение в теорию расписаний / В.С. Танаев, В.В. Шкурба. - М. : Наука, 1975.

12. Описание метода ветвей и границ [Електронний ресурс]. - Режим доступа: http://math.nsc.ru/AP/benchmarks/UFLP/uflp_bb.html

13. Гладков Л.А. Генетические алгоритмы / Л.А. Гладков, В.М. Курейчик, В.В.Курейчик. – Ростов-на-Дону : Ростиздат, 2004г.

14. Муравьиные алгоритмы [Електронний ресурс] / А.А. Кажаров, В.М.Курейчик. - Режим доступа: http://raai.org/cai-08/files/cai-08_paper_144.doc

>> зміст

Під час написання даного автореферату магістерська робота ще не завершена. Повне закінчення роботи: грудень 2009 року. Повний текст роботи та матеріали по темі можуть бути отримані в автора або його керівника після зазначеної дати.

>> зміст